package com.example.javamaday.leetcode.sort;

// 归并排序
public class LcSort0912_05 {

    private int[] helper;

    public static void main(String[] args) {

    }

    // 归并排序
    public int[] sortArray(int[] nums) {
        // 分配辅助数组的空间
        helper = new int[nums.length];
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    public void sort(int[] nums, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        sort(nums, lo, mid);  // 左部分排序
        sort(nums, mid + 1, hi);  // 右部分排序
        merge(nums, lo, mid, hi); // 归并数组
    }

    public void merge(int[] nums, int lo, int mid, int hi) {
        // 将 nums[lo...mid]和 nums[mid+1...hi]归并
        int i = lo;      // 要合并的数组起始位index
        int j = mid + 1; // 要合并的数组起始位index

        // 将数据复制到帮助数组
        for (int k = lo; k <= hi; k++) {
            helper[k] = nums[k];
        }

        // 归并数组
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                nums[k] = helper[j++];
                continue;
            } else if (j > hi) {
                nums[k] = helper[i++];
                continue;
            }
            if (helper[i] > helper[j]) {
                nums[k] = helper[j++];
            } else {
                nums[k] = helper[i++];
            }
        }
    }

}
